package com.ljx.List;

/**
 * @author 李加喜
 * @Package com.ljx.Dynamic
 * @date 2021-11-06 9:49
 */

import com.ljx.Dynamic.ListNode;

import java.util.PriorityQueue;

/**
 * 合并K个升序列表
 */
public class MergeKLists {
    public static void main(String[] args) {
        MergeKLists mergeKLists = new MergeKLists();
        int[] num={1,4,5};
    }

    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        ListNode listNode = new ListNode(-1);
        ListNode p = listNode;
        // 创建优先级队列来存储堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b) -> (a.val - b.val));
        // 将K个链表的头结点放到最小堆里面
        for (ListNode list : lists) {
            if (list != null) {
                pq.add(list);
            }
        }
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            p.next = cur;
            if (cur.next != null) {
                pq.add(cur.next);
            }
            // p向前走一位
            p= p.next;

        }
        return listNode.next;

    }
}
